package com.woldier.algorithm.hashing;

import java.util.HashMap;
import java.util.Map;

/**
 * description
 * <p>
 * 给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
 * <p>
 * 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
 * <p>
 * <p>
 * <p>
 * 示例 1 ：
 * <p>
 * 输入：nums = [2,2,1]
 * 输出：1
 * <p>
 * 示例 2 ：
 * <p>
 * 输入：nums = [4,1,2,1,2]
 * 输出：4
 * <p>
 * 示例 3 ：
 * <p>
 * 输入：nums = [1]
 * 输出：1
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 3 * 104
 * -3 * 104 <= nums[i] <= 3 * 104
 * 除了某个元素只出现一次以外，其余每个元素均出现两次。
 *
 * @author: woldier wong
 * @date: 2023/12/26$ 15:28$
 */
public class Letcode_136_SingleNumber {

    /**
     * description
     * <p>
     * 算法思想1: hash表, key记录值, value 记录索引
     * <p>
     * 然后依次遍历数组, 并且尝试将其放入map中, 这里存在三种情况
     * <p>
     * 1.key不在map中, 说明此数字第一次出现, 理应将其放入map中, map的value记录索引位置
     * <p>
     * 2.key在map中, 说明数字第二次出现, 那么我们将对应记录清除, 说明其出现了两次
     * <p>
     * 那么遍历玩数组之后, map中只有一个元素, 就是出现次数为1的
     * <p>
     * <p>
     * 算法思想2: 利用异或运算
     * <p>
     * 异或运算又三个重要性质
     * 1.任何数与0做异或任然是原数: a^0 = a
     * 2.任何数字与自己的异或结果为0: a ^ a = 0
     * 3.异或满足结合律和交换律: a ^ b ^ c = a ^ ( b ^ c)
     * <p>
     * 结合上述性质, 我们可以发现如果有一组数字它们除了有一个数是出现1次外, 其他都出现两次
     * 那么 可以写成 如下形式 a ^ b ^ c ^ a ^ c = (a ^ a) ^ (b ^ b) ^ c = 0 ^ c = c
     *
     * @param nums
     * @return int
     * @author: woldier wong
     * @date: 2023/12/26 15:34
     */
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i]; //得到对应数组
            if (!map.containsKey(num)) {
                map.put(num, i); //不存在, 放入
            } else {
                map.remove(num); //存在, 说明num是第二次出现, 那么将其移除
            }
        }
        Object[] array = map.keySet().toArray();
        return (int) array[0];
    }

    public int singleNumberV2(int[] nums) {
        int single = 0;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i]; //得到对应数组
            single ^= num;
        }
        return  single;
    }

}
